// Package day_12_dp 6-63
// @Title day_12_dp
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/6 16:08
// @Create  2021/9/6 16:08
package day_12_dp

// UniquePathsWithObstacles 有障碍物的路径和
func UniquePathsWithObstacles(obstacleGrid [][]int) int {
	dp := make([][]int, len(obstacleGrid))
	rowFalse := 1
	for i := range obstacleGrid {
		dp[i] = make([]int, len(obstacleGrid[0]))
		if obstacleGrid[i][0] == 1 {
			rowFalse = 0
		}
		dp[i][0] = rowFalse
	}
	colFalse := 1
	for i := 0; i < len(obstacleGrid[0]); i++ {
		if obstacleGrid[0][i] == 1 {
			colFalse = 0
		}
		dp[0][i] = colFalse
	}
	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[0]); j++ {
			if obstacleGrid[i][j] == 1 {
				dp[i][j] = 0
			} else {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}
